# optimiser.rb
# Copyright (c) 2009 Alex Wilson
# Licensed under the MIT license (see LICENSE in the distribution root dir)

require "timetable"
require "rubygems"

module Timetable
  module Optimisation
    # Represents a combination of course/series/group options that make
    # up a possible timetable.
    # 
    # This is, in fact, an Array of integers that index into the list
    # of groups belonging to each series.
    class Option < Array
      # Hash of explanation => penalty pairs explaining how the score was 
      # calculated, filled after Option#fitness is run
      attr_reader :trace
      @@fit_cache = Hash.new
      @@trace_cache = Hash.new
      
      # Constructs a new Option, indexing the given series, with their
      # maximum indices given in the array max.
      #
      # All other parameters are treated as in Array.new
      def initialize(series, max, *k)
        super(*k)
        @series = series
        @max = max
      end
      
      # Returns the next possible combination of groups after this one
      # (or this Option's 'successor') -- does add-and-carry on the 
      # integers in the array.
      def next
        child = Option.new(@series, @max, self.size, 0)
        s = size
        # copy to child
        i = 0
        while i < s
          child[i] = self[i]
          i += 1
        end
        
        # do carry and add
        child[0] += 1
        i = 0
        while i < (s - 1)
          if (child[i] == @max[i])
            child[i+1] += 1
            child[i] = 0
          end
          i += 1
        end
        
        # final reset if we've carried over
        if (child[s-1] == @max[s-1])
          child[s-1] = 0
        end
        
        return child
        
      end
      
      # Turns this Option into an array of Timetable::Group objects, which
      # it represents.
      def groups
        c = Array.new
        i = 0
        while i < self.size
          c << @series[i].groups.values[self[i]]
          i += 1
        end
        c
      end
      
      # Possible penalty metrics
      PENALTIES = %w(clash nobreak 2hour 3hour lonely 8am late)
      PENALTY_DESCS = ["Clash", "No break between classes", "Break >= 2 hours", 
        "Break >= 3 hours", "Only one class on an entire day", 
        "8am start", "Late finish (after 6pm)"]
      PENALTY_DEFAULTS =   { 'clash' => 0.7, 'nobreak' => 0.04, '2hour' => 0.02, 
        '3hour' => 0.12, 'lonely' => 0.12, '8am' => 0.06, 'late' => 0.05 }
      
      # Calculates the fitness function for this individual using
      # the weighted rule scheme.
      #
      # Takes the current maximum value, and the settings hash of weights.
      # The former is used for branch-pruning to improve performance, the
      # latter for the actual weighting.
      #
      # The values in settings will override those in PENALTY_DEFAULTS.
      #
      # This function will return the fitness score as calculated, and also set
      # up the value of trace to contain a hash detailing how the score was
      # calculated.
  		def fitness(current_max=0.00, settings=nil)
  		  
  		  # default settings
  		  settings = PENALTY_DEFAULTS if not settings
  		  
  		  @trace = @@trace_cache[[self,settings]] if @@trace_cache[[self, settings]]
  		  return @@fit_cache[[self,settings]] if @@fit_cache[[self,settings]]
  		  @trace = []
  			grps = groups

  			score = 1.0
  			sz = self.size

        # Penalise clashes
        # One clash should be enough to make sure it can't be best
        i = 0
        while i < sz
          g = grps[i]
          j = i + 1
          while j < sz
            g2 = grps[j]
            if g.clash_weight(g2) > 0.00
              return (@@fit_cache[[self, settings]] = 0.00)
            end
            j += 1
          end
          i += 1
        end
  		
  					
  					#penalty = settings['clash'] * g.clash_weight(g2)
            #score -= penalty
            #if score <= current_max
            #  return @@fit_cache[[self,settings]] = score
            #end
  					#@trace << { 
  					#  :desc => "clash: #{g.course} #{g.series}#{g.number} with #{g2.series}#{g2.number}", 
  					#  :penalty => penalty } if penalty > 0

  			sessions = Array.new
  			i = 0
  			while i < grps.size
  			  g = grps[i]
  			  j = 0
  			  while j < g.sessions.size
  			    s = g.sessions[j]
  			    sessions << s if not sessions.include?(s)
  			    j += 1
			    end
  			  i += 1
			  end

        # Do time rules -- don't want long breaks, don't want
        # many-hour runs.
  			sessions.each do |s|
  				til,s2 = s.next_of(sessions)
  				if s2
  					case
  						when til < (1.0/24)
  						  @trace << {
  						    :desc => "no break: #{s.course} #{s.series}#{s.number}",
  						    :penalty => settings['nobreak']
  						  }
  							score -= settings['nobreak']
  							if score <= current_max
                  return @@fit_cache[[self,settings]] = score
                end
  						when til > (3.0/24)
  						  @trace << {
  						    :desc => ">3hr break: #{s.course} #{s.series}#{s.number}",
  						    :penalty => settings['3hour']
  						  }
  							score -= settings['3hour']
  							if score <= current_max
                  return @@fit_cache[[self,settings]] = score
                end
  						when til > (2.0/24)
  						  @trace << {
  						    :desc => ">2hr break: #{s.course} #{s.series}#{s.number}",
  						    :penalty => settings['2hour']
  						  }
  							score -= settings['2hour']
  							if score <= current_max
                  return @@fit_cache[[self,settings]] = score
                end
  					end
  				end
  				
  				# Do same days rule -- don't want only one thing on a given day
  				same_days = s.same_day_as(sessions)
  				if same_days.size == 0 
  				  @trace << {
					    :desc => "alone on #{DateTime::ABBR_DAYNAMES[s.start.wday]}: #{s.course} #{s.series}#{s.number}",
					    :penalty => settings['lonely']
					  }
  				  score -= settings['lonely']
  				  if score <= current_max
              return @@fit_cache[[self,settings]] = score
            end
				  end
				  
          # Do start/finish rules
          if (s.start.hour < 9)
            score -= settings['8am']
            if score <= current_max
              return @@fit_cache[[self,settings]] = score
            end
            @trace << {
              :desc => "8am start: #{s.course} #{s.series}#{s.number}",
              :penalty => settings['8am']
            }
          end
          if (s.finish.hour == 17 and s.finish.min > 10) or (s.finish.hour > 17)
            score -= settings['late']
            if score <= current_max
              return @@fit_cache[[self,settings]] = score
            end
            @trace << {
              :desc => "late finish: #{s.course} #{s.series}#{s.number}",
              :penalty => settings['late']
            }
          end
  			end

  			score = 0.0 if score < 0.0
  			
  			@@trace_cache[[self,settings]] = @trace
  			@@fit_cache[[self, settings]] = score
  		end
      
    end
    
    # The optimiser factory class for performing timetable
    # optimisation
    class Optimiser
      # Takes series, an array of Timetable::Series objects that are to be 
      # optimised over, and config, a Hash of weights
      def initialize(series, config)
        @series = series
        @config = config
        @check_mutex = Mutex.new
        Option::PENALTIES.each do |p|
          if not config[p]
            config[p] = Option::PENALTY_DEFAULTS[p]
          else
            config[p] = config[p].to_f
          end
        end
      end
      
      # Returns the current best option
      def best
        @best_option
      end
      
      # Returns the score of the current best option
      def best_score
        @best_score
      end
      
      # Returns the trace of the current best option
      def best_trace
        @best_option.trace
      end
      
      # Performs the optimisation
      def run
        max = Array.new
        i = 0
        while i < @series.size
          series = @series[i]
          groups = series.groups.keys
          max << groups.size
          i += 1
        end
        puts max.inspect
        total = max.inject { |prod, n| prod*n }
        
        first_option = Option.new(@series, max, Array.new(@series.size, 0))
        @best_option = first_option
        @best_score = @best_option.fitness(0.00, @config)
        @count = 0
        threads = Array.new
        
        this_option = first_option.next
        while this_option != first_option
          threads << Thread.new(this_option) do |option|
            #puts "new thread #{Thread.current}"
            #puts "doing option #{option.inspect}"
            score = option.fitness(@best_score, @config)
            @check_mutex.synchronize do
              @count += 1
              if score > @best_score
                @best_score = score
                @best_option = option
              end
            end
          end
          if (threads.size == 20)
            #puts "cleaning up thread #{threads[0]}"
            threads[0].join()
            threads.delete_at(0)
            perc = "%.02f" % ((@count.to_f / total.to_f)*100)
            yield "#{perc}% ", @best_score if block_given? and @count % 100 == 0
          end
          this_option = this_option.next
        end
        threads.each do |th|
          th.join()
        end
      end
    end
  end
end
    
